Решение задачи достижимости в графе с заданными ограничениями в виде многокомпонентной контекстно-свободной грамматики с использованием умножения матриц
Аннотация:
Предмет исследования. Многие задачи анализа графов могут быть сформулированы как задачи поиска путей с ограничениями в виде формальных языков. В последнее время задача достижимости в графе с заданными ограничениями в виде контекстно-свободных языков стала очень популярной и используется во многих областях, например, для запросов к графовым базам данных, для анализа RDF (Resource Description Framework) данных. Однако некоторые сложные ограничения на пути в графе не могут быть описаны с помощью контекстно-свободных языков, поэтому были предложены различные расширения. Многокомпонентные контекстно-свободные языки — одно из таких расширений. В данной работе представлены результаты разработки первого алгоритма поиска путей в графе с заданными ограничениями в виде многокомпонентных контекстно-свободных языков. Метод. Сущность предложенного алгоритма состоит в использовании набора булевых матриц и операций над ними для поиска путей в графе, удовлетворяющих заданным ограничениям. Основной операцией является умножение булевых матриц. В качестве результата алгоритм возвращает набор матриц, содержащий всю информацию, необходимую для решения задачи достижимости в графе с заданными ограничениями в виде многокомпонентного контекстно-свободного языка. Основные результаты. Представленный алгоритм реализован на языке Python с использованием стандарта GraphBLAS. Выполнен анализ реальных RDF данных и синтетических графов для некоторых классических многокомпонентных контекстно-свободных языков. Исследование показало, что при использовании разреженного формата для хранения матриц и параллельных вычислений для графов с десятками тысяч ребер время анализа может составлять 10–20 минут. Результат проведенного анализа представляет десятки миллионов пар достижимых вершин. Практическая значимость. Разработанный алгоритм может быть применен в задачах статического анализа программ, в биоинформатике, в сетевом анализе, а также в графовых базах данных, когда ограничения на пути в графе не могут быть выражены с помощью контекстно-свободных грамматик. Алгоритм основан на операциях линейной алгебры, что позволяет использовать высокопроизводительные библиотеки и задействовать современные параллельные вычислительные системы.
Ключевые слова:
Постоянный URL
Статьи в номере
- Полимерная композиция с фенантренхиноном для записи рельефных голографических решеток
- Современные методы математического моделирования в биомедицинских исследованиях
- Анализ фазовых изображений, полученных при использовании голографической системы регистрации на основе эффекта геометрической фазы и поляризационной камеры
- Система цветоделения на основе цветового треугольника для колориметрических исследований в микроскопии
- Концепция регистрации изображений с использованием двухэлементного активного оптико-электронного комплекса
- Вариационная задача адаптивного оптимального управления. Теоретический и прикладной компьютерный анализ
- Краткий обзор развития теорий робастности, грубости и бифуркаций динамических систем
- Предсказание результатов 16-факторного теста Р. Кеттелла на основе анализа текстовых постов пользователей социальной сети
- Методика управления компонентами распределительной электроэнергетической системы при обеспечении качества потребляемой электроэнергии
- Голосовая система оценки ответов для учащихся с ограниченными физическими возможностями, использующих обработку естественного языка и машинное обучение
- Обнаружение вредоносного домена на основе естественного языка с использованием машинного обучения и глубокого обучения
- Гибридный алгоритм JAYA для планирования рабочих процессов в облаке
- Информационная модель продолжительности покупки товаров первой необходимости
- Разработка технологии интерактивной мобильной поддержки пациентов с хроническими заболеваниями
- Выделение ролей в сетях общественного транспорта с атрибутами узлов: описание модели
- Обзор систем обнаружения сетевых вторжений, основанных на подходах глубокого обучения
- Мониторинг состояния здоровья населения по возрастным группам
- Модель аналитики энергопотребления на основе интеллектуальной оболочки Game Optimization для данных интеллектуального учета
- Метод активного демпфирования напряжения с отрицательной обратной связью по току звена постоянного тока в электрических и гибридных электрических трансмиссиях
- Сравнительный анализ методов управления вентильно-индукторной электрической машиной
- Газовая динамика стационарных сверхзвуковых газовых струй с инертными частицами при их истечении в среду с низким давлением
- Смешанные формы свободных колебаний прямоугольной CFCF-пластины
- Моделирование тепло-гидродинамических процессов в испарителях низкотемпературных систем с внутриканальным кипением хладагентов
- Высокопроизводительное моделирование напряженно-деформированного состояния тонкостенных оболочечных конструкций с использованием глубокого обучения
- Валидация автоматных спецификаций